public class Test54 {
    //逆中序遍历方式
    private static int ans = 0, count = 0;
    public static int kthLargest(TreeNode root, int k) {
        dfs(root, k);
        return ans;
    }

    private static void dfs(TreeNode root, int k) {
        if (root.right != null) dfs(root.right, k);

        if (++count == k) {
            ans = root.val;
            return;
        }

        if (root.left != null) dfs(root.left, k);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.val = 5;
        root.left = new TreeNode();
        root.left.val = 3;
        root.right = new TreeNode();
        root.right.val = 7;
        root.left.left = new TreeNode();
        root.left.left.val = 2;
        root.left.right = new TreeNode();
        root.left.right.val = 4;
        root.right.left = new TreeNode();
        root.right.left.val = 6;
        root.right.right = new TreeNode();
        root.right.right.val = 8;

        System.out.println(kthLargest(root, 3));
    }
}
